package com.yjc.dp;

/**
 * 392. 判断子序列
 *
 * @author yjc
 * @create 2024-07-23 11:14
 */
public class Subject_6 {
    public static void main(String[] args) {
        String s = "axc";
        String t = "ahbgdc";

        int n = t.length();
        int m = s.length();
        int j = 0;

        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (j == m) {//找到了子串，直接结束
                System.out.println(true);
                return;
            }
            dp[i] = dp[i - 1];//将最大匹配结果转移给下一个
            if (s.charAt(j) == t.charAt(i - 1)) {//s的第 j 项匹配到了，j下标++
                dp[i] = dp[i - 1] + 1;
                j++;
            }
        }


        //比较结果，看是否匹配子串长度
        System.out.println(dp[n] == m ? true : false);

    }
}
